import java.util.Arrays;

public class LeetCode322 {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;  // 用于表示一个很大的数，方便后续进行最小值的比较
        int[] dp = new int[amount + 1];  // dp[i]表示构成金额i所需的最小硬币数量
        Arrays.fill(dp, max);  // 初始化dp数组，将所有金额的最小硬币数量都设为一个很大的值
        dp[0] = 0;  // 初始条件：0金额需要0个硬币

        // 从1到amount遍历每一个金额i
        for (int i = 1; i <= amount; i++) {
            // 遍历所有硬币面额
            for (int j = 0; j < coins.length; j++) {
                // 如果当前硬币的面额小于等于i，那么可以尝试使用该硬币
                if (coins[j] <= i) {
                    // 更新dp[i]，选择使用硬币coins[j]的最小硬币数
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }

        // 如果dp[amount]仍然是一个很大的值，说明无法用给定硬币组成amount
        return dp[amount] > amount ? -1 : dp[amount];
    }

//    收米呢嗯 selenium
}
